package practice1_100;

import thread.AAA;

import java.util.Arrays;
import java.util.Scanner;
public class AAAA {
    protected void test(String a){
        System.out.println(a);
    }
    public static AAA aaa=new AAA();
    public static void main(String[] args) {
        AAAA aaaa=new AAAA();
        AAAA aaaa1=new AAAA();

    }
    public static boolean isPerfectSquare(int num) {
        //二分法
        Long left =0L,right=(long)num;
        Long mid=0L;
        while(left<=right){
            mid=(right+left)/2;
            if(mid*mid==num)return true;
            else if(mid*mid<num){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return false;
    }
    public static int minCostClimbingStairs(int[] cost) {
        if(cost.length==1)return cost[0];
        if(cost.length==2)return Math.min(cost[0],cost[1]);
        int res[]=new int[cost.length+1];
//        res[0]=cost[0];res[1]=cost[1];
        for(int i=2;i<res.length;i++){
            res[i]=Math.min(res[i-1]+cost[i-1],res[i-2]+cost[i-2]);
        }
        return res[res.length-1];
    }
//

    public static int rob(int[] nums) {
        if(nums.length==1)return nums[0];
        int[] left= Arrays.copyOfRange(nums,0,nums.length-1);
        int[] right= Arrays.copyOfRange(nums,1,nums.length);
        return Math.max(method(left),method(right));
    }

    public static int method(int[] temp){
        if(temp.length==1)return temp[0];
        if(temp.length==2)return Math.max(temp[0],temp[1]);
        int[] res=new int[temp.length];
        res[0]=temp[0];res[1]=Math.max(temp[0],temp[1]);
        for(int i=2;i<temp.length;i++){
            res[i]=Math.max(res[i-1],res[i-2]+temp[i]);
        }
        return res[res.length-1];
    }

    public static boolean canJump(int[] nums) {
        if(nums.length==1)return true;
        boolean res[]=new boolean[nums.length];
        res[0]=true;
        for(int i=1;i<nums.length;i++){
            for(int j=i-1;j>=0;j--){
                if(res[i]==true)break;
                res[i]=(i-j<=nums[j]&&res[j])||res[i];
            }
        }
        return res[res.length-1];
    }
}
